// https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
// 4. Median of Two Sorted Arrays
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    // 保证 nums1 的长度不大于 nums2
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    /**
     * 所谓有序数组的中位数，它左右两侧的元素个数是相等的。
     * nums1: 0, 1, 2, ..., i-1, i, i+1, ..., m, i 表示中位数，left: [0, i-1]，right: [i, m]
     * nums2: 0, 1, 2, ..., j-1, j, j+1, ..., n. j 表示中位数，left: [0, j-1], right: [j, n]
     */

    const m = nums1.length;
    const n = nums2.length;
    const isOdd = ((m + n) & 1) === 1;
    let left = 0;
    let right = m;
    let median1 = 0;
    let median2 = 0;
    while (left <= right) {
        const i = (left + right) >> 1;
        const j = ((m + n + 1) >> 1) - i;

        const ai_1 = i === 0 ? -Infinity : nums1[i - 1];
        const ai = i === m ? Infinity : nums1[i];
        const bi_1 = j === 0 ? -Infinity : nums2[j - 1];
        const bi = j === n ? Infinity : nums2[j];

        if (ai_1 < bi) {
            median1 = Math.max(ai_1, bi_1);
            median2 = Math.min(ai, bi);
            left = i + 1;
        } else {
            right = i - 1;
        }
    }

    if (isOdd) {
        return median1;
    }
    return (median1 + median2) / 2;
}

export { findMedianSortedArrays };
